package developer.算法.子串.滑动窗口最大值;

import java.util.*;

/**
 * @author zhangyongkang
 * @time 2025/3/13 17:00
 * @description 给你一个整数数组 nums，
 * 有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。
 * 你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
 * <p>
 * 返回 滑动窗口中的最大值 。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
 * 输出：[3,3,5,5,6,7]
 * 解释：
 * 滑动窗口的位置                最大值
 * ---------------               -----
 * [1  3  -1] -3  5  3  6  7       3   8 3 +1
 * 1 [3  -1  -3] 5  3  6  7       3
 * 1  3 [-1  -3  5] 3  6  7       5
 * 1  3  -1 [-3  5  3] 6  7       5
 * 1  3  -1  -3 [5  3  6] 7       6
 * 1  3  -1  -3  5 [3  6  7]      7
 * 示例 2：
 * <p>
 * 输入：nums = [1], k = 1
 * 输出：[1]
 */
public class Huadongchuangkongzuidazhi {

    public static void main(String[] args) {
//        int[] ints = maxSlidingWindow(new int[]{1, 3, -1, -3, 5, 3, 6, 7}, 3);
        System.out.println(Arrays.toString(maxSlidingWindow_self_cankao(new int[]{1, 3, -1, -3, 5, 3, 6, 7}, 3)));
//        System.out.println(Arrays.toString(ints));
    }


    //参考官方答案自己写一遍
    public static int[] maxSlidingWindow_self_cankao(int[] nums, int k) {
        //巧用队列
        //思路如下
        /**
         * 1. 维护一个队列从尾部进行添加 对数组进行正向遍历
         * 2. i> j 如果 j>i 那么当i在的时候  j必在 所以如果num[j]>num[i]  那么  i不可能是最大的数 所以直接移除
         * 3. 保证当前队列的头是最大的数据
         * 4. 剔除掉已经超过窗口的头数据
         */
        Deque<Integer> deque = new LinkedList<>();
        int index = 0;
        int[] result = new int[nums.length - k + 1];
        for (int i = 0; i < k; i++) {
            while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {//如果当前值是大于最后一个值的  那么后续这两个窗口所在的最大值不可能是上一个值
                deque.pollLast();
            }
            deque.addLast(i);
        }
        result[index++] = nums[deque.peekFirst()];
        for (int i = k; i < nums.length; i++) {

            //做两个操作  写入最大值  以及弹出 头部已经超出窗口的值
            while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {//如果当前值是大于最后一个值的  那么后续这两个窗口所在的最大值不可能是上一个值
                deque.pollLast();
            }
            deque.addLast(i);

            while (deque.peekFirst() <= (i - k)) {
                deque.removeFirst();
            }
            result[index++] = nums[deque.peekFirst()];

        }
        return result;
    }

    public static int[] maxSlidingWindow(int[] nums, int k) {
        int arrLength = nums.length;
        int loopNums = arrLength - k + 1;
        int[] result = new int[loopNums];
        for (int i = 0; i < loopNums; i++) {
            int left = i;
            int right = i + k - 1;
            Integer max = null;
            for (int j = left; j <= right; j++) {
                int num = nums[j];
                if (max == null) {
                    max = num;
                } else {
                    max = Math.max(max, num);
                }
            }
            if (max != null) {
                result[i] = max;
            }

        }
        return result;
    }

    /**
     * 对于「最大值」，我们可以想到一种非常合适的数据结构，那就是优先队列（堆），其中的大根堆可以帮助我们实时维护一系列元素中的最大值。
     * <p>
     * 对于本题而言，
     * 初始时，我们将数组 nums 的前 k 个元素放入优先队列中
     * 。每当我们向右移动窗口时，我们就可以把一个新的元素放入优先队列中，
     * 此时堆顶的元素就是堆中所有元素的最大值。然而这个最大值可能并不在滑动窗口中，
     * 在这种情况下，这个值在数组 nums 中的位置出现在滑动窗口左边界的左侧。
     * 因此，当我们后续继续向右移动窗口时，这个值就永远不可能出现在滑动窗口中了，我们可以将其永久地从优先队列中移除。
     * <p>
     * 我们不断地移除堆顶的元素，直到其确实出现在滑动窗口中。
     * 此时，堆顶元素就是滑动窗口中的最大值。为了方便判断堆顶元素与滑动窗口的位置关系
     * ，我们可以在优先队列中存储二元组 (num,index)，
     * 表示元素 num 在数组中的下标为 index。
     * <p>
     * 作者：力扣官方题解
     * 链接：https://leetcode.cn/problems/sliding-window-maximum/solutions/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     *
     * @param nums
     * @param k
     * @return
     */
    public int[] maxSlidingWindow_official_1(int[] nums, int k) {
        int n = nums.length;
        PriorityQueue<int[]> pq = new PriorityQueue<int[]>(new Comparator<int[]>() {
            public int compare(int[] pair1, int[] pair2) {
                return pair1[0] != pair2[0] ? pair2[0] - pair1[0] : pair2[1] - pair1[1];
            }
        });
        for (int i = 0; i < k; ++i) {//先把队列中推入数据
            pq.offer(new int[]{nums[i], i});
        }
        int[] ans = new int[n - k + 1];//返回值的数量
        ans[0] = pq.peek()[0];//初始答案
        for (int i = k; i < n; ++i) {
            pq.offer(new int[]{nums[i], i});//推入第k+1个选项
            while (pq.peek()[1] <= i - k) {//判定当前第首位是否在当前的窗口中，如果不在则剔除
                pq.poll();
            }
            ans[i - k + 1] = pq.peek()[0];
        }
        return ans;
    }

    /**
     * 我们可以顺着方法一的思路继续进行优化。
     * <p>
     * 由于我们需要求出的是滑动窗口的最大值，
     * 如果当前的滑动窗口中有两个下标 i 和 j，其中 i 在 j 的左侧（i<j），
     * 并且 i 对应的元素不大于 j 对应的元素（nums[i]≤nums[j]），那么会发生什么呢？
     * <p>
     * 当滑动窗口向右移动时，只要 i 还在窗口中，那么 j 一定也还在窗口中，这是 i 在 j 的左侧所保证的。
     * 因此，由于 nums[j] 的存在，nums[i] 一定不会是滑动窗口中的最大值了，我们可以将 nums[i] 永久地移除。
     * <p>
     * 因此我们可以使用一个队列存储所有还没有被移除的下标。
     * 在队列中，这些下标按照从小到大的顺序被存储，并且它们在数组 nums 中对应的值是严格单调递减的。
     * 因为如果队列中有两个相邻的下标，它们对应的值相等或者递增，那么令前者为 i，后者为 j，
     * 就对应了上面所说的情况，即 nums[i] 会被移除，这就产生了矛盾。
     * <p>
     * 当滑动窗口向右移动时，我们需要把一个新的元素放入队列中。为了保持队列的性质，
     * 我们会不断地将新的元素与队尾的元素相比较，如果前者大于等于后者，那么队尾的元素就可以被永久地移除，我们将其弹出队列。我们需要不断地进行此项操作，直到队列为空或者新的元素小于队尾的元素。
     * <p>
     * 由于队列中下标对应的元素是严格单调递减的
     * ，因此此时队首下标对应的元素就是滑动窗口中的最大值。但与方法一中相同的是，此时的最大值可能在滑动窗口左边界的左侧，
     * 并且随着窗口向右移动，它永远不可能出现在滑动窗口中了。
     * 因此我们还需要不断从队首弹出元素，直到队首元素在窗口中为止。
     * <p>
     * 为了可以同时弹出队首和队尾的元素，我们需要使用双端队列。满足这种单调性的双端队列一般称作「单调队列」。
     * <p>
     * <p>
     * <p>
     * 作者：力扣官方题解
     * 链接：https://leetcode.cn/problems/sliding-window-maximum/solutions/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     *
     * @param nums
     * @param k
     * @return
     */

    public int[] maxSlidingWindow_official_2(int[] nums, int k) {
        int n = nums.length;
        Deque<Integer> deque = new LinkedList<>();
        for (int i = 0; i < k; ++i) {
            while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {
                deque.pollLast();
            }
            deque.offerLast(i);
        }

        int[] ans = new int[n - k + 1];
        ans[0] = nums[deque.peekFirst()];
        for (int i = k; i < n; ++i) {
            while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {
                deque.pollLast();
            }
            deque.offerLast(i);
            while (deque.peekFirst() <= i - k) {
                deque.pollFirst();
            }
            ans[i - k + 1] = nums[deque.peekFirst()];
        }
        return ans;
    }


}
